package com.justnow.offer;

import java.util.*;

/**
 * @author justnow
 * Created on 2020-09-18
 * Description
 *
 * 购物组合
 * 时间限制： 3000MS
 * 内存限制： 589824KB
 * 题目描述：
 * 便利店有价格不等的多种商品，假定价格都是正整数且每种商品的数量都是无限多的；用户手上有特定金额的钱，计算有多少种不同方式可以把钱花光。
 *
 *
 *
 * 输入描述
 * public int buy(int money, int[] items)
 *
 * 说明：
 *
 * money：用户拥有的总金额
 *
 * items：商品价格数组
 *
 * 输出描述
 * 返回：购物组合数量
 *
 *
 * 样例输入
 * 5
 * 1,2,5
 * 样例输出
 * 4
 *
 * 提示
 * 解释：
 * 5=5
 * 5=2+2+1
 * 5=2+1+1+1
 * 5=1+1+1+1+1
 *
 */
public class BiLiFeng03 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        String str = scanner.nextLine();

        String[] split = str.split(",");
        int[] array = new int[split.length];
        for (int i = 0; i < split.length; i++) {
            array[i] = Integer.valueOf(split[i]);
        }

        int length = array.length;
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();

        dfs(array, 0, length, n, path, res);
        System.out.println(res.size());
    }

    private static void dfs(int[] array, int begin, int length, int target, Deque<Integer> path, List<List<Integer>> res) {
        if (target < 0) {
            return ;
        }
        
        if (target == 0) {
            res.add(new ArrayList<>(path));
        }

        for (int i = begin; i < length; i++) {
            path.addLast(array[i]);
            dfs(array, i, length, target - array[i], path, res);
            path.removeLast();
        }

    }
}
